package LeetCode;
//给你一个字符串 s，找到 s 中最长的 回文 子串。
//
//
//
//        示例 1：
//
//        输入：s = "babad"
//        输出："bab"
//        解释："aba" 同样是符合题意的答案。
//        示例 2：
//
//        输入：s = "cbbd"
//        输出："bb"
//
//
//        提示：
//
//        1 <= s.length <= 1000
//        s 仅由数字和英文字母组成
public class Code05_longestPalindrome {

    /**
     * 寻找给定字符串中的最长回文子串
     * 该方法使用动态规划来解决问题，通过构建一个二维数组dp来记录回文子串的信息
     * dp[i][j]表示字符串s在[i, j]区间内是否为回文子串，如果是，则dp[i][j]的值为dp[i-1][j-1]+1，否则为0
     * 最终返回最长回文子串
     *
     * @param s 输入的字符串
     * @return 最长回文子串如果不存在，则返回null
     */
    public static String longestPalindrome(String s) {
        // 检查输入字符串是否为空或长度为0，如果是，则返回null
        if (s == null || s.length() == 0){
            return null;
        }
        // 将输入字符串转换为字符数组
        char[] chars1 = s.toCharArray();
        // 将输入字符串反转，用于后续比较
        StringBuilder sb = new StringBuilder(s);
        sb = sb.reverse();
        char[] chars2 = sb.toString().toCharArray();
        // 初始化动态规划数组
        int[][] dp = new int[chars1.length][chars1.length];
        // 初始化最长回文子串的长度和结束位置
        int max = 0;
        int right = 0;
        // 初始化动态规划数组的第一列
        for (int i = 0; i < chars1.length; i++) {
            dp[i][0] = chars1[i] == chars2[0] ? 1 : 0;
        }
        // 初始化动态规划数组的第一行
        for (int j = 0; j < chars1.length; j++) {
            dp[0][j] = chars1[0] == chars2[j] ? 1 : 0;
        }
        // 动态规划填充剩余部分，寻找最长回文子串
        for (int i = 1; i < chars1.length; i++) {
            for (int j = 1; j < chars2.length; j++) {
                if (chars1[i] == chars2[j]){
                    dp[i][j] = dp[i-1][j-1] + 1;
                    // 更新最长回文子串的长度和结束位置
                    if (max < dp[i][j]){
                        max = dp[i][j];
                        right = i;
                    }
                }
            }
        }
        // 根据最长回文子串的结束位置和长度，返回该子串
        return s.substring(right - max + 1, right + 1);
    }


    public static void main(String[] args) {
        String s = "babad";
        System.out.println(longestPalindrome(s));
        System.out.println(longestPalindrome("cbba"));
        System.out.println(longestPalindrome("ababc"));
    }
}
